package 尊享面试.哈希;

import java.util.*;

public class a249移位字符串分组 {
    static class Solution {
        public List<List<String>> groupStrings0(String[] strings) {
            Arrays.sort(strings);
            List<List<String>> ans = new ArrayList<>();
            for (String str : strings) {
                boolean foundGroup = false;
                for (List<String> group : ans) {
                    if (group.isEmpty()) continue;
                    String first = group.get(0);
                    if (first.length() != str.length()) continue;
                    boolean isSameGroup = true;
                    int diff = (str.charAt(0) - first.charAt(0) + 26) % 26;
                    for (int i = 0; i < str.length(); i++) {
                        if (str.charAt(i) - first.charAt(i) != diff) {
                            isSameGroup = false;
                            break;
                        }
                    }
                    if (isSameGroup) {
                        group.add(str);
                        foundGroup = true;
                        break;
                    }
                }
                if (!foundGroup) {
                    List<String> list = new ArrayList<>();
                    list.add(str);
                    ans.add(list);
                }
            }
            return ans;
        }

        public List<List<String>> groupStrings(String[] strings) {
            Map<String, List<String>> map = new HashMap<>();
            for (String str : strings) {
                StringBuilder sb = new StringBuilder();
                char first = str.charAt(0);
                for (int i = 0; i < str.length(); i++) {
                    int dif = (str.charAt(i) - first + 26) % 26;
                    sb.append(dif).append("#");
                }
                map.computeIfAbsent(sb.toString(), k -> new ArrayList<>()).add(str);
            }
            return new ArrayList<>(map.values());
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] strings = {"abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"};
        List<List<String>> ans = solution.groupStrings(strings);
        System.out.println(ans);
    }
}
